package 我的Java学习_算法基础.day_03;

import java.util.Arrays;

public class 归并排序_递归 {
    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

        mergeSort(a, 0, 9);

        System.out.println(Arrays.toString(a));

    }

    /**
     * @param a     待排序数组
     * @param left  指向第一个元素
     * @param right 指向最后一个元素
     */
    public static void mergeSort(int[] a, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(a, left, mid);
            mergeSort(a, mid + 1, right);
            merge(a, left, mid, right);
        }
    }

    /**
     * 将左右两边有序子数组合并
     *
     * @param a     待排序数组
     * @param left  指向第一个索引
     * @param mid   指向中间的索引
     * @param right 指向最后一个索引
     */
    public static void merge(int[] a, int left, int mid, int right) {

        //创建辅助数组
        int[] arr = new int[right - left + 1];
        //左指针
        int l = left;
        //右指针
        int r = mid + 1;
        //临时数组的指针
        int k = 0;
        //将两个数组有序合并到辅助数组中
        while (l <= mid && r <= right) {
            if (a[l] < a[r]) {
                arr[k++] = a[l++];
            } else {
                arr[k++] = a[r++];
            }
        }
        //将剩下的还没有存入arr的数按顺序存入临时数组
        while (l <= mid) {
            arr[k++] = a[l++];
        }
        while (r <= right) {
            arr[k++] = a[r++];
        }
        //将排序好的临时数组替换掉原来的数组
        for (int i = 0; i < k; i++) {
            a[left++] = arr[i];
        }
    }
}

